package leetcode.code0516;

import leetcode.helper.MaxDebug;

public class Solution extends S516 {

	@Override
	public int longestPalindromeSubseq(String s) {
		char[] chars = s.toCharArray();
		int Len = chars.length;
		int[][] dp = new int[Len][Len];
		for (int i = Len - 1; i >= 0; i--) {
			dp[i][i] = 1;
			for (int j = i + 1; j < Len; j++) {
				dp[i][j] = chars[i] == chars[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i][j - 1], dp[i + 1][j]);
			}
		}
		return dp[0][Len - 1];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		MaxDebug.debug14(so);
	}

}
